import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        // 快速排序
        int[] nums = {2, 3, -1, 0, 9, 10};
        QuickSort qs = new QuickSort();
        qs.quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    // 思想：
    // 1. 找一个基准值
    // 2. j先从最右找小于基准值的停止 i再从最左向最右找大于基准值的停止  如果 i < j 交换位置  一直循环这个过程  直到 i == j
    // 3. 如果i下标的值小于基准值，交换位置  然后将数组分成 小于基准值的  和 大于基准值的两部分
    // 4. 小于基准值和大于基准值的两部分分别进行 1， 2， 3
    public void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int i = left;
        int j = right;
        int jiZhun = arr[left]; // 1. 找一个基准值
        // 一直循环这个过程  直到 i == j
        while (i != j) {
            // j先从最右找小于基准值的停止
            while (i < j && arr[j] >= jiZhun) {
                j --;
            }

            // i再从最左向最右找大于基准值的停止
            while (i < j && arr[i] <= jiZhun) {
                i++;
            }

            // 如果 i < j 交换位置
            if (i < j) {
                arr[j] = arr[i] ^ arr[j];
                arr[i] = arr[i] ^ arr[j];
                arr[j] = arr[i] ^ arr[j];
            }
        }

        // 如果i下标的值小于基准值，交换位置
        if (arr[i] < jiZhun) {
            arr[left]= arr[i];
            arr[i] = jiZhun;
        }

        // 然后将数组分成 小于 基准值的 （arr, left, i - 1） 和 大于基准值的两部分  （arr, i + 1, right）
        // 小于基准值和大于基准值的两部分分别进行 1， 2， 3
        quickSort(arr, left, i -1); // 小于基准值
        quickSort(arr, i + 1, right); // 大于基准值
    }
}
